package com.mlh.dp.背包问题.完全背包;

import java.util.HashSet;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/21 10:57
 * @DESCRIPTION
 */
// 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。
// 如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
// 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
// 输入: s = "leetcode", wordDict = ["leet", "code"]
// 输出: true
// 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
public class 单词拆分 {
    //读题目就知道是完全背包问题
    //本质是一样的，但是套的壳是变化的，所有去调整
    public boolean method1(String s, List<String> wordDict) {
        boolean[]dp=new boolean[s.length()+1];
        dp[0]=true;
        for (int i = 1; i <=s.length(); i++) {//这里将容量写在外循环中，比较好理解这题
            for (int j = 0; j < wordDict.size(); j++) {//物品种类写在内循环
                if(i>=wordDict.get(j).length()
                        &&dp[i]==false
                        //字符串匹配
                        //substring(int beginIndex, int endIndex) 从beginIndex开始，到endIndex结束截取字符串。包括start，不包括end
                        //这里的i相对于s字符串中的下标已经是+1了，例如 s中下标为3，i则已经是4了
                        &&s.substring(i-wordDict.get(j).length(),i).equals(wordDict.get(j))
                        ){
                    dp[i]=dp[i-wordDict.get(j).length()];
                }
            }
        }
        return dp[s.length()];
    }

    public boolean practice(String s, List<String> wordDict) {
        boolean[]dp=new boolean[s.length()+1];
        dp[0]=true;
        for (int i = 1; i <=s.length(); i++) {
            for (int j = 0; j < wordDict.size(); j++) {
                int strLen = wordDict.get(j).length();
                if(i>=strLen
                        && dp[i]==false
                        &&s.substring(i-strLen,i).equals(wordDict.get(j))){
                    dp[i]=dp[i-strLen];
                }
            }
        }
        return dp[s.length()];
    }
}
